#ifndef LEETCODE_CN_CPP_PROBLEMS_97_H
#define LEETCODE_CN_CPP_PROBLEMS_97_H

#include <string>
#include <vector>

using namespace std;

namespace problem_97
{

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        if ((s1.size() + s2.size()) != s3.size())
            return false;
        if (s1.empty())
            return s2 == s3;
        if (s2.empty())
            return s1 == s3;
        //dp[i][j]表示s1[0...i-1]和s2[0...j-1]能否组成s3[0...i+j-1]
        //dp[i][j]= (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
        int rows = s1.size() + 1, cols = s2.size() + 1;
        vector<vector<bool>> dp(rows, vector<bool>(cols, false));
        dp[0][0] = true;
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j)
            {
                int len = i + j;
                if (len == 0)
                    continue;
                bool ok = false;
                auto c = s3[len - 1];
                if (i - 1 >= 0)
                    ok = (ok || (dp[i - 1][j] && (c == s1[i - 1])));
                if (j - 1 >= 0)
                    ok = (ok || (dp[i][j - 1] && (c == s2[j - 1])));
                dp[i][j] = ok;
            }
        }
        return dp[s1.size()][s2.size()];
    }
};

} // namespace problem_97

#endif //LEETCODE_CN_CPP_PROBLEMS_97_H
